//************************************************************
//    > File Name: two-sum.cpp
//    > Author: davis
//    > Mail:  
//    > Created Time: 2017年03月16日 19:58:03
//***********************************************************
//lintcode #56
#include<bits/stdc++.h>
#include<string>
#include<unordered_map>
using namespace std;
vector<int> twoSum(vector<int>& nums,int target){
	vector<int> res(2,0);
	unordered_map<int, int> m;
	for(int i=0;i<nums.size();m[nums[i]]=i,++i){
		if(m.count(target-nums[i])){
			res[1]=m[target-nums[i]]+1;
			res[0]=i+1;
			return res;
		}
	}
	return res;
}
vector<int> twoSum2(vector<int>& nums,int target){
	vector<int> res(2,0);
	unordered_map<int, int> m;
	for(int i=nums.size();i--;m[nums[i]]=i){
		if(m.find(target-nums[i])==m.end()) continue;
		res[0]=i+1;
		res[1]=m[target-nums[i]]+1;
		return res;
	}
	return res;
}
int main()
{
	vector<int> m,n;
	m.resize(5);
	for(int i=0;i<m.size();++i)
		m[i]=i+1;
	//n=twoSum(m,8);
	n=twoSum2(m,8);
	for(int i=0;i<n.size();++i)
		cout<<n[i]<<" ";
	cout<<endl;
}
